package J3_11;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

public class test {
    //你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。
    //
    //如果你能使这个正方形，则返回 true ，否则返回 false 。
    //
    //

    public boolean makesquare(int[] matchsticks) {
        int sum = 0;
        for (int n : matchsticks) {
            sum += n;
        }
        if (sum % 4 != 0) {
            return false;
        }
        int side = sum / 4;
        Arrays.sort(matchsticks);
        for (int i = 0; i < matchsticks.length/2; i++) {
            int tmp = matchsticks[i];
            matchsticks[i] = matchsticks[matchsticks.length-i-1];
            matchsticks[matchsticks.length-i-1] = tmp;
        }
        int[] edges = new int[4];
        return hasPlaceLay(0,matchsticks,edges,side);
    }

    private boolean hasPlaceLay(int index, int[] matchsticks, int[] edges, int side) {
        if (index == matchsticks.length) {
            return true;
        }

        for (int i = 0; i < 4; i++) {
            edges[i] += matchsticks[index];
            if (edges[i] <= side && hasPlaceLay(index+1,matchsticks,edges,side)) {
                return true;
            }
            edges[i] -= matchsticks[index];
        }
        return false;

    }
}
